1. Field of the Invention
This invention relates generally to placing (i.e., allocating) logical data stores on an array of storage devices, and more particularly to placement such that store request time is minimized.
2. Background of the Invention
Parallel input/output (I/O) systems have been employed due to their ability to provide fast and reliable access, while supporting high transfer rates for dedicated supercomputing applications as well as diverse enterprise applications. Disk arrays are typically arranged to partition data across multiple hard disk drives within a storage pool, and provide concurrent access to multiple applications at the same time. A single application having large data requirements may further partition its data into stores and place them across multiple disks, such that the resulting parallelism alleviates the I/O bottleneck to a certain degree.
However, in modern web-services scenario where performance guarantees are in place, throughput is no longer the only performance requirement for applications. Many applications require that the average response time of their requests is maintained within certain thresholds, such that the average response time does not exceed a predetermined maximum time. Since storage latencies continue to dominate request response times, reducing the response time of a request effectively means minimizing storage latency. The high variance within service times due to the heterogeneous applications service from a disk array, combined with the non-work conserving nature of disk drives, implies that the response time of the requests of a logical data store is influenced primarily by the characteristics of other logical data stores placed on the same disk.
A logical data store can be a database table, files owned by a particular user, or data used by an application, among other types of logical data stores. A number of logical data stores may be placed over an array of parallel hard disk drives, which can be referred to as disks, or more generally as storage devices. A sequence of disk requests generated by an application or user can be denoted as a stream, and the logical data group accessed by the stream can be synonymously considered a logical data store as well.
Where there are a number of logical data stores to be placed on an array of storage devices, they are desirably placed on the storage devices such that the average response time for all store requests is minimized, and that their work load is balanced across all the storage devices. This issue also finds applications in web services, where user streams—i.e., logical data stores—are allocated to different web servers, and each server may manage its own storage. Current strategies for placing logical data stores on storage devices, however, do not minimize response.